{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Health to Beat Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumHealth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通关游戏所需的最低生命值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在玩一个有 <code>n</code> 个关卡的游戏，从 <code>0</code> 到 <code>n - 1</code>。给你一个&nbsp;<strong>下标从 0&nbsp;开始&nbsp;</strong>的整数数组 <code>damage</code>，其中 <code>damage[i]</code> 是你完成第 <code>i</code> 个关卡所损失的生命值。</p>\n",
    "\n",
    "<p>你也会得到一个整数 <code>armor</code>。你最多只能在&nbsp;<strong>任何&nbsp;</strong>等级使用&nbsp;<strong>一次&nbsp;</strong>护甲技能，这将保护你免受 <strong>最多</strong>&nbsp;<code>armor</code> 伤害。</p>\n",
    "\n",
    "<p>你必须按顺序完成关卡，并且你的生命值必须一直&nbsp;<strong>大于</strong> <code>0</code> 才能通关。</p>\n",
    "\n",
    "<p>返回<em>你开始通关所需的最低生命值。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> damage = [2,7,4,3], armor = 4\n",
    "<strong>输出:</strong> 13\n",
    "<strong>解释:</strong> 从 13 生命值开始通关游戏的最佳方法是:\n",
    "第 1 回合，受到 2 点伤害。你还有 13 - 2 = 11 生命值。\n",
    "第 2 回合，受到 7 点伤害。你还有 11 - 7 = 4 生命值。\n",
    "第 3 回合，使用你的护甲保护你免受 4 点伤害。你有 4 - 0 = 4 生命值。\n",
    "第 4 回合，受到 3 点伤害。你还有 4 - 3 = 1 生命值。\n",
    "注意，13 是你开始时通关游戏所需的最低生命值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> damage = [2,5,3,4], armor = 7\n",
    "<strong>输出:</strong> 10\n",
    "<strong>解释:</strong> 从 10 生命值开始通关游戏的最佳方法是:\n",
    "第 1 回合，受到 2 点伤害。你还有 10 - 2 = 8 生命值。\n",
    "第 2 回合，使用护甲保护自己免受 5 点伤害。你还有 8 - 0 = 8 生命值。\n",
    "第 3 回合，受到 3 点伤害。你还有 8 - 3 = 5 生命值。\n",
    "第 4 回合，受到 4 点伤害。你还有 5 - 4 = 1 生命值。\n",
    "注意，10 是你开始通关所需的最低生命值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> damage = [3,3,3], armor = 0\n",
    "<strong>输出:</strong> 10\n",
    "<strong>解释:</strong> 从 10 生命值开始通关游戏的最佳方法是:\n",
    "第 1 回合，受到 2 点伤害。你还有 10 - 3 = 7 生命值。\n",
    "第 2 回合，受到 3 点伤害。你还有 7 - 3 = 4 生命值。\n",
    "第 3 回合， 受到 3 点伤害。你还有 4 - 3 = 1 生命值。\n",
    "注意你没有使用护甲技能。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == damage.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= damage[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= armor &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-health-to-beat-game](https://leetcode.cn/problems/minimum-health-to-beat-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-health-to-beat-game](https://leetcode.cn/problems/minimum-health-to-beat-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,7,4,3]\\n4', '[2,5,3,4]\\n7', '[3,3,3]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHealth(self, damage: List[int], armor: int) -> int:\n",
    "        if max(damage)>= armor:\n",
    "            return sum(damage)-armor+1\n",
    "        \n",
    "        return sum(damage)-max(damage)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHealth(self, damage: List[int], armor: int) -> int:\n",
    "        res=0\n",
    "        maxv = -inf\n",
    "        for d in damage:\n",
    "            if d>maxv:\n",
    "                maxv = d\n",
    "            res+=d\n",
    "        return res-min(armor,maxv)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHealth(self, damage: List[int], armor: int) -> int:\n",
    "        return sum(damage) + 1 - min(max(damage), armor)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHealth(self, damage: List[int], armor: int) -> int:\n",
    "        return sum(damage) - min(armor, max(damage)) + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHealth(self, damage: List[int], armor: int) -> int:\n",
    "        return sum(damage) + 1 - min(max(damage), armor)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHealth(self, damage: List[int], armor: int) -> int:\n",
    "        damage.sort(key=lambda x:-x)\n",
    "        return sum(damage[1:])+max(damage[0]-armor,0)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHealth(self, damage: List[int], armor: int) -> int:\n",
    "        return sum(damage) - max(damage) + max(max(damage) - armor, 0) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHealth(self, damage: List[int], armor: int) -> int:\n",
    "\n",
    "        n=max(damage)\n",
    "        idt=damage.index(n)\n",
    "        result=0\n",
    "        for i in range(len(damage)):\n",
    "            if i!=idt:\n",
    "                result+=damage[i]\n",
    "            else:\n",
    "                if armor>=damage[idt]:\n",
    "                    result+=0\n",
    "                else:\n",
    "                    result+=damage[idt]-armor\n",
    "\n",
    "        return result+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHealth(self, damage: List[int], armor: int) -> int:\n",
    "        base = sum(damage) + 1\n",
    "        mx = max(damage)\n",
    "        if mx >= armor:\n",
    "            return base - armor\n",
    "        return base - mx \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
